﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 原题连接：https://www.nowcoder.com/practice/64a4c026b2aa4411984f560deec36323?tpId=196&tqId=40272&ru=/exam/oj

/*
题目描述：
体育课共有
n
u
m
P
r
o
j
e
c
t
numProject个考核项目，编号为
0
0到
n
u
m
P
r
o
j
e
c
t
−
1
numProject−1，考核中每两个项目被划分为一组得到分组数组
g
r
o
u
p
s
i
groups
i
​
 ，现规定若想完成项目
g
r
o
u
p
s
i
[
0
]
groups
i
​
 [0]，必须先完成
g
r
o
u
p
s
i
[
1
]
groups
i
​
 [1]。保证所有分组互不相同，若分组情况能顺利完成考核，请返回任意的一个完成顺序,否则返回空数组 。
数据范围：
1
≤
n
u
m
P
r
o
j
e
c
t
≤
2000
1≤numProject≤2000
1
≤
g
r
o
u
p
s
i
.
l
e
n
g
t
h
≤
n
u
m
P
r
o
j
e
c
t
∗
(
n
u
m
P
r
o
j
e
c
t
−
1
)
1≤groups
i
​
 .length≤numProject∗(numProject−1)
示例1
输入：
3,[[2,1]]
复制
返回值：
[1,2,0]
复制
说明：
要先完成1号项目，再完成2号项目，而0号项目不受约束，故可以以1 2 0的顺序完成项目。
示例2
输入：
3,[[1,0], [0,1]]
复制
返回值：
[]
复制
说明：
第一个分组要求先完成0号项目，再完成1号项目；而第二个分组要求先完成1号项目，再完成0号项目，自相矛盾，故不可以完成项目。
*/

// 开始解题：
// 方法——拓扑排序   
class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int> >& groups) {
        // 建图
        vector<vector<int>> edges(n);
        vector<int> in(n);
        for (auto& v : groups) {
            int a = v[1];
            int b = v[0];
            edges[a].push_back(b);
            in[b]++;
        }
        queue<int> q;
        vector<int> ret(n);
        int index = 0;
        // 现将所有入度为0的点加入到队列中
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            ret[index++] = cur;
            for (auto e : edges[cur]) {
                if (--in[e] == 0) {
                    q.push(e);
                }
            }
        }
        if (index == n) {
            return ret;
        }
        return { };
    }
};